import java.util.PriorityQueue;
import java.util.Queue;

class Solution {
    /**
     * 设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
     * 输入： arr = [1,3,5,7,2,4,6,8], k = 4
     * 输出： [1,2,3,4]
     * @param arr
     * @param k
     * @return
     */
    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        if (arr == null || k == 0) {
            return ret;
        }
        //O(N*logN)
        Queue<Integer> minHeap = new PriorityQueue<>(arr.length);
        for (int x : arr) {
            minHeap.offer(x);
        }
        //K*logN
        for (int i = 0;i < k;i++) {
            ret[i] = minHeap.poll();
        }
        return ret;
    }

    /**
     * 找前K个最大的元素
     * 将数组前K个元素建立小根堆 , 剩下的元素依次和堆顶元素进行比较
     * 小根堆的堆顶元素就是小根堆的最小元素 , 剩下元素比堆顶元素小,则不入堆
     * 剩下元素比堆顶元素大,则将堆顶元素放到堆尾删除, 将剩余元素放入堆顶,再  进行排序,使新堆变成小根堆
     * 以此往复 ,直到将数组元素比较结束
     * O(N*logK)
     * @param arr
     * @param k
     * @return
     */
    public int[] maxK2(int[] arr, int k) {
        int[] ret = new int[k];
        if (arr == null || k == 0) {
            return ret;
        }
        Queue<Integer> minHeap2 = new PriorityQueue<>(k);
        //1.遍历数组的前k 个元素 放到堆中 O(K*logK)
        for (int i = 0; i < k; i++) {
            minHeap2.offer(arr[i]);
        }
        //2.遍历剩下的 k-1 个 , 每次和堆顶元素进行比较
        //  当堆顶元素小的时候 , 就出堆 O(N-K)*logK
        for (int i = k; i < arr.length; i++) {
            int val = minHeap2.peek();
            if (val < arr[i]) {
                minHeap2.poll();
                minHeap2.offer(arr[i]);
            }
        }
        for (int i = 0; i < k; i++) {
            ret[i] = minHeap2.poll();
        }
        return ret;
    }
}